Digital data communications systems are commonly used to transmit and/or receive data between remote transmitting and receiving locations. A central facet of any data communications system is the reliability and integrity of the data which is being communicated. Ideally, the data which is being transmitted from the transmitting location should be identical to the data which is being received at the receiving location. Practically however, the data which is received at the receiving location has oftentimes been corrupted with respect to the original data that was transmitted from the transmitting location. Such data communication errors may be attributed in part to one or more of the transmission equipment, the transmission medium or the receiving equipment. With respect to the transmission medium, these types of data errors are usually attributed to the less than ideal conditions associated with the particular transmission medium.
To overcome these problems, data communications systems often rely on error detection and error correction schemes, to detect the occurrence of a data error and to correct a data error, respectively. One simple form of error detection is the use of a parity bit associated with each block of data to indicate whether the particular block contains an odd or even number of 1 bits. However, this is a very simple scheme which has numerous disadvantages. It is a simple type of error detection scheme which is capable of accurately detecting up to one bit error per data block. Moreover, the use of a parity bit cannot detect the occurrence of two bit errors in a data block, since this is not even detected as a parity violation. Additionally, the use of a parity bit only detects errors; it cannot correct errors. Any time that an error is detected, the receiving location typically requests retransmission of the particular data block from the transmitting location.
One type of error correction scheme commonly used in data communications systems is the use of redundant data transmissions and a voting circuit at the receiving location. In such a system, the data being transmitted is repeated a number of times, such as five. At the receiving location, all five data blocks are received and processed by a voting circuit which compares the five received versions of each data bit and determines the bit to be a 1 or 0 based on the voting consensus. Although such a system is capable of detecting and correcting data errors, it does so at a great cost in terms of the effective data throughput or transmission rate. This is due to the fact that each data block must be repeated a number of times.
The above-mentioned correction/detection schemes are examples of binary block codes. Specifically, an (n,k,d) binary block code is a set of 2.sup.k binary codewords of block length n and minimum distance d (i.e., coding distance). The transmitted data is partitioned into binary blocks of length k, then each block is mapped into a binary codeword of length n, which is then modulated and transmitted through the channel. This block code is capable of correcting up to t=(d-1)/2 errors within each codeword. As mentioned above, there are cases where channel errors occur in non-frequent bursts, the length of which exceeds the error correction capability of the code. These cases are handled by interleaving the data stream before it is modulated and transmitted through the channel. Functionally, an interleaver is a memory device which is used to rearrange and separate the codewords or frames which are to be transmitted. The terms codeword and frame are used interchangeably herein where a frame includes only one codeword. Instead of transmitting a succession of complete codewords, the interleaver allows the transmission of a portion (such as a byte) of a first codeword, followed by a portion of a second codeword, and so on. Henceforth, these portions will be referred to as either symbols or codeword symbols. In this way, if an error burst occurs during transmission, the error burst will not be localized to one particular frame. Rather, the errors will be spread across several codewords. If the errors were completely within one codeword, they may exceed the number of errors which the system can inherently correct for by the use of a block code. By spreading the data errors across several blocks, the number of errors within each block may be reduced to the point where the system is capable of correcting the data errors.
In a simple interleaver, data is written into the memory in columns and then read out in rows for subsequent transmission. At the receiver end, the received data is written into a de-interleaver in rows and then read out in columns. The interleaver rearranges the data within the codewords, and the de-interleaver essentially performs the reverse process to reconstruct the codewords for subsequent use. In this type of interleaver, all the data write operations are carried out as a group, and then the data read operations are carried out as a group. This type of interleaving, referred to as block interleaving, introduces latency of one block at the transmitter and one block at the receiver, due to the fact that a complete block has to be written before it can be read.
Another type of interleaver, referred to as a convolutional interleaver, has been introduced (J. S. Ramsey, "Realization of Optimum Interleavers", IEEE Trans. on Information Theory, Vol. IT-16, No. 3, pp. 338-345, May, 1970, the contents of which are incorporated herein by reference) as a means of reducing the latency incurred in block interleaving by one-half. In the convolutional interleaver, the individual read and write operations are alternated instead of being carried out all at once as a group of write operations followed by a group of read operations. Additionally, in the convolutional interleaver, the read operation following a write operation begins at the next memory location following where the write operation left off. This aspect of convolutional interleavers will be described in more detail with reference to FIG. 1 which shows the memory structure of a convolutional interleaver. As shown in FIG. 1, a convolutional interleaver memory 10 is configured to have R rows, numbered 1 through R, and C columns, numbered 1 through C. A codeword of frame which enters the interleaver is spread and reordered at the interleaver output. The size of R is often chosen to correspond to the number of symbols in a codeword or frame which is to be transmitted, while the size of C determines the interleaving depth which is the number of codeword frames over which a transmitted codeword at the interleaver input is spread by the interleaving process at the interleaver output. The memory locations of interleaver memory 10 are labelled for reference purposes as: (1,1) for the upper left memory location; (R,1) for the lower left memory location; (1,C) for the upper right memory location; and (R,C) for the lower right memory location. The selection of the specific dimensions R and C for any particular application is constrained such that R and C cannot have a common multiple factor (except for 1, of course). In a given application where R and C do have a common multiple factor, P. T. Tong, T. N. Zogakis and J. M. Cioffi, "Revised FEC and Interleaving Recommendations for DMT ADSL", ANSI T1E1.4/93-117, May 10, 1993, the contents of which are incorporated herein by reference, propose the addition of a "dummy" symbol, that is not actually transmitted, to the beginning of each codeword frame at the interleaver input. This artificially increases the R dimension, such that R and C do not have any common multiple factors. These "dummy" symbols are used primarily to maintain proper memory pointers and addresses, as discussed in detail below, and are extracted prior to data transmission so as not to consume a portion of the usable bandwidth of the system. Similar "dummy" symbols are used in the de-interleaver.
For example, in the case where R=151, C=10 and the codewords are thus 151 symbols long, the first operation performed by the interleaver is to write the first codeword into the interleaver memory 10 starting at location (1,1) and continuing to location (151,1). Next, a read operation is performed starting at the next memory location following the last symbol of the previously written codeword. In general, "wrap around" techniques are used to determine the next memory location for subsequent operations, as well as when the end of a column is reached. The wrap around may be either within the same column, or to the next column. Thus, in the case of wrap around within the same column, after the first write operation described above, the first read operation is performed beginning at location (1,1). If wrap around to the next column were used, the read operation would start at location (2,1). The description given herein will be in terms of wrap around within the same column; the principles of operation are equally applicable to wrap around to the next column. Alternatively, these write/read operations may be performed on a sub-codeword basis, such as a symbol, i.e., after each symbol is written, a symbol is read.
Beginning at location (1,1), the read operation is performed in rows. Since there are 10 symbols per row and the read operation will read 151 symbols, this corresponds to the first 15 full rows and the first symbol in row 16, i.e., locations (1,1) through (16,1). Because at this stage only the first column has valid data written into it, most of the data read out from the interleaver memory will be "garbage". Next, a write operation is performed beginning at the next location following the last read operation. Since the last read operation was at location (16,1), the write operation begins at location (16,2) and continues until the end of column 2 is reached (i.e., location (151,2)). At this point, a wrap around is performed to the top of the same column, i.e., location (1,2) and the write operation continues until location (15,2). Thus, the second block of data is written into the second column of the interleaver memory 10; however, the starting point is not the top of the column, but rather the 16th symbol of the column.
Next, a read operation is performed starting at the next location after the last write operation. Since the last write operation was at location (15,2), the read operation begins at location (16,2) and continues reading in rows, through location (31,2). This is followed by a write operation beginning at location (31,3) and continuing through location (30,3). The process is repeated until the interleaver memory 10 has been filled with valid data. It is thus apparent that the convolutional interleaver staggers the starting symbol for each column of data in the interleaver memory.
Data errors which occur during transmission typically affect a contiguous group of data symbols being transmitted. This can be viewed conceptually as the corruption of one or more consecutive rows of data in the interleaver memory. It will be recalled that data is read out from the interleaver memory in rows for subsequent transmission. The deleterious effects of data transmission errors are reduced in the first place by the operation of the interleaver. Instead of transmitting a succession of complete codewords, the interleaver transmits a series of symbols, one from each codeword. In this way, the effects of an error burst which lasts for a certain period of time, will be spread across several codewords. Thus, for example, if 20 consecutive symbol errors occur, they will not all be concentrated in one codeword, and instead may be manifested as one errored symbol in each of 20 codewords. By spreading the errors out over many codewords, the number of errored symbols in any given block will hopefully be reduced to a level that can be corrected by the inherent error correction capabilities of the particular coding scheme being used. In the above example, if a coding scheme which can correct up to four errored symbols per codeword is used, such a coding scheme will be overwhelmed if an interleaver is not used and 20 symbol errors occur in the same block. If instead, an interleaver is used, then the number of errors in each codeword may be reduced to four or less, within the error correction capabilities of the code.
Oftentimes it is desirable to group several "codewords" of data into a single frame. This is typically the case in certain transmission schemes where the frame rate is fixed, but it is desired to increase the overall number of codeword symbols being transmitted per frame. Typically, the size of the codewords cannot be increased beyond a certain maximum size. Thus, one approach that has evolved is to combine several codewords into a single frame. However, the combination of several codewords into a single frame presents certain problems when used with an interleaver. The straightforward approach to combining codewords in an interleaver is to simply write the complete codewords, one after the other, into the columns of the interleaver memory. However, in the case where smaller codewords are used, their error correcting capability is correspondingly reduced. Thus, since each codeword occupies a contiguous section of a column, if the rows affected by the data errors all occur within that section of the column, again, the error correcting capability of the code will be overwhelmed.
One solution to the above problem is to interleave the individual codewords in a frame before the frame data is input to the main interleaver described above. Essentially, this is a two level interleaving process. Thus, for example, if there are two codewords per frame, then the interleaver memory for each column would be filled with alternate symbols from the two codewords; if there are three codewords per frame, then the interleaver memory will be filled with a symbol from each of the three codewords in turn, so that the individual codewords will be spread out over every third symbol in the column. In this way, a burst of data errors occurring in a series of contiguous rows will be evenly spread over the alternated codewords within a column. However, this approach is disadvantageous in that a larger memory is needed to store the parallel codewords. Additional processing is also required to perform the alternating process.